In an information search system such as a search engine, an inverted index is used as a core data structure. FIG. 1 illustrates an example of a structure of the inverted index. The inverted index is constituted by a list (vocabulary) of terms and a list of postings (posting list) of each term as illustrated in FIG. 1. In addition, each posting contains a document ID and a term frequency in a corresponding document. For example, a word “Wikipedia” is contained in documents #3, #4, #5, #6, and #7 and the word is discovered 8 times in the document #6.
As a search environment is diversified and becomes dynamic, such a management technique of the inverted index is researched a lot and a past management technique has been developed by keeping a hard disk drive (HDD) in mind as a storage medium of the inverted index. As well known, since the HDD shows a very slow response speed in a random access, an update strategy of the inverted index concentrates on avoiding a random access.
However, in recent years, the flash solid state disk (SSD) is on the rise as a strong alternative of the HDD. The flash SSD is adopted in a wide area due to excellent performance including short access latency, energy efficiency, a high bandwidth, and the like.